#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	//sort()
using namespace std;

#define VSIZE 100000

#include<ctime>
#include<cstdlib>	//abort	bsearch
#include<stdio.h>	//snprintf

int CompareString(const void* a, const void* b) {
	if (*(string*)a > *(string*)b)
		return 1;
	
	else if (*(string*)a < *(string*)b)
		return -1;

	else
		return 0;
}

void tTest_Vector() {
	//没有指定大小, 默认是0, 当空间不够时, 两倍增长
	//当增长时, 重新分配内存, 并搬运元素
	vector<string> v;

	clock_t timeStart = clock();
	cout << "开始时间: " << timeStart << endl;

	char buf[10];
	for (int i = 0; i < VSIZE; i ++) {
		try {
			snprintf(buf, 10, "%d", rand());	//根据格式化得到字符串
			v.push_back(buf);
		}
		catch (exception& p) {
			cout << "i= " << i << " "<< p.what() << endl;
			abort();	//退出程序
		}
	}

	cout << "赋值所需要时间: " << clock() - timeStart << endl;
	cout << "vector 大小: " << v.size() << endl;
	cout << "vector 起点元素: " << v.front() << endl;
	cout << "vector 终点元素: " << v.back() << endl;
	cout << "vector 起点地址: " << v.data() << endl;
	cout << "vector 分配大小: " << v.capacity() << endl;

	string target;
	cin >> target;

	//全局的 find() 函数, 循序查找
	timeStart = clock();
	vector<string>::iterator pItem = ::find(v.begin(), v.end(), target);	//返回结果为一个迭代器
	cout << "::find 所需要时间: " << clock() - timeStart << endl;

	if (pItem != v.end())
		cout << "找到元素: " << *pItem << endl;
	else
		cout << "找不到" << endl;

	//排序 sort (c++)
	timeStart = clock();
	sort(v.begin(), v.end());
	cout << "sort 所需要时间: " << clock() - timeStart << endl;

	//二分查找 (先排序) bsearch (c)
	timeStart = clock();
	string *dest = (string*)bsearch(&target, v.data(), VSIZE, sizeof(string), CompareString);
	cout << "bsearch 所需要时间: " << clock() - timeStart << endl;

	if (dest != NULL)
		cout << "找到元素: " << *dest << endl;
	else
		cout << "找不到" << endl;
}